package hot100;

public class Rob {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;

        if (nums.length == 1) return nums[0];

        //假设从0开始偷
        int n = nums.length;
        int[] dp = new int[n];//dp[i]代表偷到这个位置的最大值

        for (int i = 0; i < n; i++) {
            dp[i] = nums[i];
        }

        int res = Math.max(dp[0],dp[1]);
        for (int i = 2; i < n; i++) {
            for (int j = i - 2; j >= 0; j--) {
                dp[i] = Math.max(dp[i],dp[j] + nums[i]);
            }
            res = Math.max(res,dp[i]);
        }

        return res;
    }
}
